package Offer03;

import java.util.*;

/**
 * 数组中重复的数字
 *
 * @author 23737
 * @time 2021.10.16
 */
public class Test {
    public static void main(String[] args) {
        int[] a = new int[]{2, 3, 1, 0, 2, 5, 3};
        System.out.println(new SolutionFour().findRepeatNumber(a));
    }
}

/**
 * 数组遍历，思想挺好的
 */
class Solution {
    public int findRepeatNumber(int[] nums) {
        int[] count = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            count[nums[i]]++;
            if (count[nums[i]] > 1) {
                return nums[i];
            }
        }
        return 0;
    }
}

/**
 * 使用哈希表来解题
 */
class SolutionTwo {
    public int findRepeatNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                return nums[i];
            }
            map.put(nums[i], 1);
        }
        return 0;
    }
}

/**
 * 使用数组的排序来解题
 */
class SolutionThree {
    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                return nums[i];
//                break;
            }
        }
        return 0;
    }
}

/**
 * 使用set来解决
 */
class SolutionFour {
    public int findRepeatNumber(int[] nums) {
        HashSet<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (hashSet.contains(nums[i])) {
                return nums[i];
            }
            hashSet.add(nums[i]);
        }
        return 0;
    }
}




